package com.order.www;

/**
 * Creared with IntelliJ IDEA.
 * Description:有一个长度为 n 的非降序数组，比如[1,2,3,4,5]，将它进行旋转，即把一个数组最开始的若干个元素搬到数组的末尾，变成一个旋转数组，
 * 比如变成了[3,4,5,1,2]，或者[4,5,1,2,3]这样的。请问，给定这样一个旋转数组，求数组中的最小值。
 * User:yxd
 * Date:2022-01-30
 * Time:21:59
 */
public class Array2 {
    public static void main(String[] args) {
        int[] array = {4,5,1,2,3};
        System.out.println(minNumberInRotateArray(array));
    }
    public static int minNumberInRotateArray(int [] array) {
        if(array == null || array.length == 0)return 0;
        int left = 0;
        int right = array.length - 1;
        int mid = 0;
        while(array[left] >= array[right]){//首先保证这不是一个升序的数组
            if(right - left == 1){//当数组只剩一个元素，也是结束此循环的条件
                mid = right;
                break;
            }
            mid = left + ((right - left) >> 1);
            if(array[left] == array[right] && array[mid] == array[left]){//前中后三个值都相等，需要遍历来寻找
                int a = array[left];
                for(int i = left + 1;i < right;i ++){
                    if(array[i] < a){
                        a = array[i];
                    }
                }
                return a;
            }
            //旋转数组前半部分是有序的，后半部分也是有序的，只需找到后半部分的开头即可，需要找到一个小于前半部分小于后半部分的值
            if(array[mid] >= array[left]){
                left = mid;
            }else {
                right = mid;
            }
        }
        return array[mid];
    }
}
